package com.cobla.struct.lineartable;

import lombok.AllArgsConstructor;
import lombok.Data;
import lombok.NoArgsConstructor;

/**
 * 单链表
 * @date 2019/8/24
 * @author wt
 */
@Data
@NoArgsConstructor
@AllArgsConstructor
public class Lnode {

    private int data;
    private Lnode next;

    /**
     * 合并链表，传入另一个链表，返回合并后的链表 <br/>
     * 头指针不包含元素
     * @param b
     * @return
     */
    public static Lnode merge(Lnode a, Lnode b){
        Lnode c = a;

        Lnode p = a.next;
        Lnode q = b.next;

        Lnode r;
        c.next = null;
        r = c;

        while (p != null && q != null) {
            if (p.data <= q.data) {
                r.next = p;
                p = p.next;
            } else {
                r.next = q;
                q = q.next;
            }
            r = r.next;
        }

        if (p.next != null) {
            r.next = p;
        }
        if (q.next != null) {
            r.next = q;
        }
        return c;
    }

    /**
     * 尾插法建立链表
     * @param a
     * @param n a 实际上存储的元素个数
     * @return
     */
    public static Lnode createListR(int a[], int n) {
        Lnode head = new Lnode(0, null);
        Lnode tail = head;
        for (int i = 0; i < n; i++) {
            tail.next = new Lnode(a[i], null);
            tail = tail.next;
        }
        tail.next = null;
        return head;
    }

    /**
     * 头插法建立链表
     * @param a
     * @param n a 实际上存储的元素个数
     * @return
     */
    public static Lnode createListF(int a[], int n) {
        Lnode head = new Lnode(0, null);

        for (int i = 0; i < n; i++) {
            head.next = new Lnode(a[i], head.next);
        }
        return head;
    }

    /**
     * 合并 a, b 并返回递减链表<br/>
     * 只需要更改 merge function 中的 过程为头插法就行了
     * @param a
     * @param b
     * @return
     */
    public static Lnode mergeDecrease(Lnode a, Lnode b) {
        Lnode c = a;

        Lnode p = a.next;
        Lnode q = b.next;

        Lnode r;
        c.next = null;

        while (p != null && q != null) {
            if (p.data <= q.data) {
                r = p;
                p = p.next;
            } else {
                r = q;
                q = q.next;
            }
            r.next = c.next;
            c.next = r;
        }

        while (p.next != null) {
            r = p;
            p = p.next;
            r.next = c.next;
            c.next = r;
        }

        while (q.next != null) {
            r = q;
            q = q.next;
            r.next = c.next;
            c.next = r;
        }
        return c;
    }

    /**
     * 例题: 通过头节点C 找到一个值为x 的节点，找到了删除，并返回状态码1表示成功，0表示失败
     * @param c
     * @param x
     * @return
     */
    public static int findAndDelete(Lnode c, int x){
        while (c.next != null) {
            if (c.next.data == x) {
                c.next = c.next.next;
                return 1;
            }
        }
        return 0;
    }

    /* 循环链表部分 */

}
